Aller au contenu

Méthodes de points intérieurs

Un article de Wikipédia, l'encyclopédie libre.
Visualisation de la méthode des points intérieur : le chemin reste à l’intérieur du polyèdre.
Visualisation de la méthode du simplexe : le chemin suit les arêtes du polyèdre
Visualisation de la méthode par ellipsoïde : l’ellipse se rétrécit

Les méthodes de points intérieurs forment une classe d’algorithmes qui permettent de résoudre des problèmes d’optimisation mathématique. Elles ont l'intérêt d'être polynomiales lorsqu'on les applique aux problèmes d'optimisation linéaire, quadratique convexe, semi-définie positive ; et plus généralement aux problèmes d'optimisation convexe, pourvu que l'on dispose d'une barrière auto-concordante représentant l'ensemble admissible, calculable en temps polynomial (ce n'est pas toujours le cas, car certains problèmes d'optimisation convexe sont NP-difficiles (voir Problème NP-complet)).

Les méthodes de points intérieurs se répartissent en plusieurs familles[1] :

  • les méthodes de chemin central
  • les méthodes de réduction de potentiel
  • les méthodes « affine scaling »

Et pour quasiment chacune de ces approches, on peut considérer une version primale, une version duale, une version primale-duale, et une version auto-duale.

Les premiers essais de résolutions de problèmes d’optimisations linéaires ont lieu dans les années 40, en même temps que l’introduction de l’Algorithme du simplexe par George Dantzig. Des algorithmes sont alors développés, notamment par von Neumann[2], Hoffman[3] et Frisch[4]. Cependant, le niveau de complexité mathématique de chaque étape ainsi que des tests décevants par rapport aux performances du simplexe font que cette méthode sera délaissée au profit de la méthode du simplexe[5].

Il faudra attendre 1984 que Narendra Karmarkar développe le premier algorithme (algorithme de Karmarkar) réellement efficace pour l’optimisation linéaire, qui s’exécute en opérations (où et le nombre de bits d’entrée de l’algorithme)[6]. Karmarkar annonce que son algorithme peut être jusqu’à 40 fois plus rapide que les algorithmes à base de simplexe de l’époque[7]. À l’opposé de l’algorithme du simplexe, cette méthode atteint l’optimum du problème en passant par l’intérieur de l’ensemble des solutions réalisables[8].

Dans la décennie qui suit, les méthodes par points intérieurs deviennent très populaires comme alternative aux méthodes basées sur l’algorithme du simplexe, et une forme de compétition entre les deux approches émerge[5]. Les méthodes par points intérieurs attirent car elles s’exécutent généralement en moins d’étapes de calcul, et sont plus rapides sur des tests réels que l’état de l’art sur le simplexe[9].

Description du problème

[modifier | modifier le code]

On a un système de m inégalités linéaires, et une fonction objectif qu’on cherche à maximiser.

Description de l’algorithme

[modifier | modifier le code]

Par méthode du chemin central

[modifier | modifier le code]

On commence par introduire une nouvelle classe de fonction, dépendant d’un paramètre µ : . On remarque que, quand , on retrouve la fonction objectif de départ : . La partie suivant de µ dans la formule est appelée fonction barrière. Son rôle est de réduire la valeur de près des frontières, pour éviter de trop s’en rapprocher[1].

L’idée générale de cette méthode est assez simple. On commence par choisir une valeur de µ suffisamment grande, un point de départ à l’intérieur des solutions possibles (en général intelligemment choisi, c’est-à-dire pas trop loin du maximum de ), et on va ensuite procéder par petits pas[10] :

  • On réduit légèrement la valeur de µ
  • On trouve une nouvelle approximation du max de . Cette nouvelle approximation peut se faire efficacement en partant de principe que le nouveau maximum reste proche du point de départ
  • On répète cette opération jusqu’à ce que µ soit suffisamment petit.

Article connexe

[modifier | modifier le code]

Références

[modifier | modifier le code]
  1. a et b Bernd Gärtner, Understanding and using linear programming, Springer, (ISBN 978-3-540-30717-4, 3-540-30717-6 et 3-540-30697-8, OCLC 184984491, lire en ligne)
  2. (en) John von Neuman, « On a maximization problem. », Technical rep ort, Institute for Advanced Study,‎
  3. (en) A. J. Hoffman,, M. Mannos, D. Sokolowsky et N. Wiegman, « Computational exp erience in solving linear programs. », Journal of the Society for Industrial and Applied Mathematics,‎
  4. (en) K. R. Frisch, « The logarithmic potential method of convex programming. », Technical report, University Institute of Economics,‎
  5. a et b (en) Erling D. Andersen Z, Jacek Gondziox, Csaba Mészáros et Xiao jie Xuk, « Implementation of Interior Point Metho ds for Large Scale Linear Programming », Technical Rep ort 1996.3,‎ (lire en ligne)
  6. (en) N. Karmarkar, « A new polynomial-time algorithm for linear programming », Combinatorica, vol. 4, no 4,‎ , p. 373–395 (ISSN 1439-6912, DOI 10.1007/BF02579150, lire en ligne, consulté le )
  7. Yinyu Ye, Interior point algorithms : theory and analysis, Wiley, (ISBN 0-471-17420-3 et 978-0-471-17420-2, OCLC 36746523, lire en ligne)
  8. Gabriel Peyré, « Interior Point Methods », sur nbviewer.org (consulté le )
  9. (en) « Interior-point method for LP - Cornell University Computational Optimization Open Textbook - Optimization Wiki », sur optimization.cbe.cornell.edu (consulté le )
  10. (en) Tamás Terlaky, « An easy way to teach interior-point methods », European Journal of Operational Research, vol. 130, no 1,‎ , p. 1–19 (ISSN 0377-2217, DOI 10.1016/S0377-2217(00)00094-1, lire en ligne, consulté le )